from IPython.display import Audio
Audio("Models of Computation_ Finite State Machines and Beyond.mp3")Can AI teach me better than a professor could?
Using Notebook LM to teach me something I didn’t understand the first time

The very first time I ever heard of Notebook LM was in my Neuroscience and Society class last semester and it was because the guest lecturer sent us a podcast he made via Notebook LM. It was cray because it was about the topic he was going to guest lecture about and he made it to make it seem like it was actually his voice as well. It’s crazy how advanced these AI tools are nowadays. As Penn is considered a research university, I feel as though the information we are taught can be very specific and research oriented. Being a Cog Sci major, I find this to be the case often, as a lot of the things that I feel I am taught can be very niche and difficult to find resources for to understand the material outside of just the professor teaching it.
One of these things I feel like I was struggling to find reliable outside resources for, was finite state machines. Don’t ask me NOTHING about what they do. I’m familiar with what they are based on how I learned about them but I couldn’t even tell you how to set one up for real to be honest (Don’t tell my major advisor). Today I decided to use Notebook LM to try to create a podcast for me to understand them better and see if I get it more than twhen the professor taught it. I uploaded the same resources the professor & TA used to teach it to us, to see if it will do a better job at spinning that same information into a way that will make more sense.
For those that are unfamiliar with what a finite state machine is, it is basically a computational model that can represent many systems or problems and contains these states that represent their “parts”. Each state is kind of dictated by a rule that needs to be met in order to get to the next state or else it’s just rejected and remains at the same state.
Input

As inputs, I put in 1) the lecture slides where I was learning about finite state machines in my intro Cog Sci class and 2) the recitation slides where the TA talked about them and gave the solutions so that the notebook could understand their premise and how they work/should be “solved”. For the prompt, I asked it “Can you make a podcast explaining what finite state machines are? How do they work and how to make them?”
Output
This is what it produced
Ever find yourself kind of wrestling with a really complex idea, like maybe something about computers, or how our own brains actually process information, like step by step? Yeah, well, today we’re diving into really a fundamental concept, something that shows up in the most unexpected places. We’re talking about the finite state machine, okay? And you could think of it as, like, a way to understand these systems, right? Yeah, it can only be in a certain number of specific conditions, and then how they shift between those based on, like, what’s happening to them. That’s
right. And you know, while it might sound a little abstract at first, the concept of a finite state machine, or FSM, is really practical, right? It’s a core building block and so many technologies we use every day, and it can even, you know, give us a really interesting way to think about, like, how we might process information ourselves, right? Yeah. But our aim here isn’t to get, you know, too technical. We want to provide a clear understanding of this idea, and especially if you’re encountering it for the first time, maybe as a college student. Our sources today are even from, like, introductory cognitive science stuff. So, so that’s right,
our mission is to explain these finite state machines in a way that, like, you know, if you’re a college student, you’re just seeing this concept maybe for the first time in a course about computation, or even, you know, how the mind works, right? You’ll finish this and have a really good grasp of what they are and, more importantly, why they matter Absolutely.
So let’s jump right in what is a finite state machine.
All right, so let’s unpack this. So at its core is this model that describes how a system computes, or, you know, behaves by moving through a specific, very limited number of states. And you can think of a state, you know, as like a distinct snapshot, or a condition that the system can be in at any given time. Okay,
I see, so what triggers that movement, that transition from one state to another? So that’s where input information
comes in. So when the machine gets some kind of input, it could be anything. It could be a signal, it could be data. It could be data, it could be a command. It shifts from its current state to a new one, and it does that following a specific rule. And the key here, obviously, in the name, is that the number of these possible states is finite. Finite. You’re right. It’s a limited set, yeah. And you might also hear it called a finite state automaton or FSA. It’s essentially the same idea. It’s just a different term, yeah, invites you when you’re reading the
finite aspect is really, really important, yeah, because it distinguishes FSMS from other models that are more complex, and those can have, you know, potentially unlimited memory or states to to make this less abstract, let’s think of a classic, very relatable example, okay, the 25 cent gumball machine. Oh, yes, that only takes nickels, okay? The trusty gumball machine. So think about the different amounts of money that could be inside the machine. As you’re putting in your nickels, right? You can have zero cents, then five, then 1015, 20, and finally, 25 and at that point, boom,
gumball. So here we’ve got, you know, a finite number of states, six representing all those different amounts. So
how does the machine transition between these states? Yeah,
so the input here is the nickel worth five cents, right? So if it’s in the zero sense state. Let’s call that the start, okay, right? And you put it in the nickel, it moves to the five cent state. Another nickel, it goes to 10 cents and so on. So each nickel you put in Acts as that trigger to move to the next state in this sequence,
within this gumball machine analogy, are any of these states
particularly significant? Definitely. So the 25 cent state, right? That’s the one we one we all want. That’s when you get the gumball Exactly. So we call that an accepting state. The machine’s done its job, right? It’s accepted enough input, in this case, nickels, to get to its goal. Right? We also have something called the initial state, which is just where the machine starts before it gets any input. So in the gumball machine, that’s the zero sense state, and very often that’s labeled as Q of zero, right? So
we’re starting to see those, those basic pieces, yeah, we’ve got a limited number of states. We’ve got movements between them that are driven by input. Now, to be a bit more formal about this, what are the components that define a finite state machine,
right? So when we talk about the formal definition, there are four key elements, and you’ll usually see these outlined in your introductory materials, like the cognitive science resources we’re using today. The first is a representation of input, and as we’ve talked about, that could be all sorts of things. So for the gumball machine, it was nickels. But in other systems, it could be, you know, letters of the alphabet, it could be digital signals, it could be user commands, anything that that machine is designed to handle, okay? The second really important component is a finite set of states, right? And you know, you’ve been talking about that a lot, but within this finite set, there are a few. Important types of states. So we have a starting state, as we said, often shown as Q show, then we have a set of accepting states. There could be one, there could be many. If the machine, you know, processes everything, all the input, and ends up in one of these accepting states. Well, that means that the initial sequence was, you know, accepted by the machine, right? So in our gumball machine, Q 25 that’s our accepting state. That’s the one who wants, one we want pay off exactly. Now, what about states that aren’t accepting states, right? What about those? So they are, you know, in effect, rejecting states, yeah, if there’s no further input, right? So if it goes through everything and it ends in a non accepting state. Well, that input sequence is considered rejected, right? And sometimes the machine might even enter what we can think of as like a dead state, which is a rejecting state, from which it’s impossible to ever reach an accepting state. Oh, wow. So like, imagine if our gumball machine somehow got into a state of like, 30 cents, okay? And only accepted nickels, yeah, it’d be stuck. Yeah, it’d be stuck. All right, that makes sense. So what’s the third key component?
The third component is a specification of state transitions. Okay? So this is basically like the rule book. It dictates very precisely where the machine will move next based on its current state and the input that it gets. And we can actually represent these rules using notation, something like this, yeah, you have the less than sign, then current state, comma input, greater than sign, right arrow, and then next state. Okay, so it’s a really clear way to see the behavior. Could
you give us an example from the gumball machine, again, using that notation absolutely
so if the machine is currently in the 10 cent state, which you know, we could label Q, 10, right, and it receives as input a nickel, five cents, the transition would look like this, less than sign Q, 10. Comma, five greater than sign right. Arrow, Q, 15. Gotcha. So you can see the machine is moving from the 10 cent state to the 15 cent states, very clear upon receiving a nickel, all right? And
the fourth and final component. So the fourth one is the concept of undefined transitions. Okay? So what happens if it’s in a particular state and it gets some input that there’s just no rule for? So our sources say in that case, the machine basically it crashes right or rejects that input sequence, okay, right, then and there. So you know, in our simple gumball machine, that only takes nickels, let’s say it’s in the Q 20 state, and for some reason it gets a dime, right? 10 cents. There’s probably no transition to find for that, right? So listen, sign, Q 20, comma, 10 greater than sign, right arrow, question mark,
right it leads to rejection. Rejection Exactly. So we have these four components, right input, then the states, including the start state and accepting states a set of rules for those transitions, and we know that undefined transitions usually lead to rejection. Now, one really interesting thing about finite state machines that you often hear emphasize when you’re learning about them is their memory less nature. So what does that actually mean, practically for how these machines operate?
Okay, this is a very important thing to understand, right? When we say it’s memoryless, it means it doesn’t keep any record of its past, right? It doesn’t remember the steps that got it to its current state. All that it knows is the state that it is in right now, okay, and the input that it’s getting right now. I
see, could you give us an example of that, of the memoryless aspect, using the gumball machine again,
of course. So imagine the machine is currently in the Q 15 state. Okay, so it’s got 15 cents worth of nickels in there. It could have gotten there by getting three nickels in a row, right? Five, five. Or maybe somebody put in one nickel, and then a bunch of other stuff happened, and then they put another nickel, you know, five, and then something and five, and then something and then five, or maybe even a dime and then a nickel, if we were allowing dimes, right, right? The point is, the machine itself doesn’t know, and it doesn’t care how it got to that Q 15 state. It doesn’t remember that history. It doesn’t remember that exactly. Its future behavior, how it acts when it receives the next nickel is only determined by the fact that it is currently in that Q 15 state, right? Not by how it got there. So
this lack of memory, it makes the design and analysis of FSMS much simpler. But as our stasis point out, it also means that there are some fundamental limits to what they can do absolutely right?
They’re good at things where the next step depends only on the current condition and what’s coming in right now, right? But they have trouble with tasks that require remembering things over longer periods or a sequence of events.
This brings us to a connection between FSMS and language, yeah, as it’s often talked about in computer science and linguistics. So how do Finite State Machines? Relate to that concept of a
language, all right, so in this context, a language means a specific set of strings, and strings are just sequences of symbols, you know, put together in order, and those are constructed from a finite alphabet. So that alphabet could be something basic, like open, curly brace, zero, comma, one, close, curly brace, or open curly brace. A, comma, B, close, curly brace. It could even be a set of instructions for a computer. Okay. The main thing is that some of those possible strings might be valid or acceptable, you know, according to a set of rules, which is the grammar of the language, right, and others wouldn’t be. So
how does an FSM come into play when we’re talking about, you know, defining or recognizing a language. So
for a language, yeah, that you can define with a finite set of rules, you can design an FSM that will accept all the strings that belong to that language and reject all the ones that don’t. Okay. So the way it does this is essentially reads the input string. It scans it, yeah, scans it from left to right, one symbol at a time. And
as we talked about earlier, whether the strings accepted or rejected depends on the state the machine is in after it’s processed the whole thing exactly.
So after reading the very last symbol of that string, if the machine is in one of its accepting states, right, then that string is part of the language, right? So it’s accepted, but if it ends in like a non accepting state, or it ran into some undefined transition somewhere along the way, then it’s rejected. It’s not part of that language that the FSM was designed to recognize. So our
sources give us an example. They mention a language L equals open, curly brace, epsilon above AB above and so on. Close, curly brace, where epsilon just means the empty string, so a string with no symbols, yeah. Can we imagine what an FSM that recognizes that language might look like? Yeah?
So that language is any sequence made up of zero or more of those AB pairs, right? So you can think of an FSM with a couple of states, right? With starting an accepting state to account for, you know, the empty string, right, zero pairs of AB, okay, if it reads an A, it goes to a second state, which is not accepting. Then if, when it’s in that second state, it reads a B, it transitions back to the first state, the accepting state. Now, if at any point it reads a B when it’s in that first state. So it’s expecting an A to start the pair, right? Or if it’s in the second state, you know, just read an a and it reads another a instead of the B, right? It would end up in a non accepting state, yeah, after it goes through the whole thing, and that means it rejects it.
So this ability to, you know, accept some sequences, reject others, really shows how FSMS can can be used to define and recognize these patterns within these strings of symbols, right? But as we mentioned earlier, there are limitations, yeah, especially when we’re talking about something as complicated as human language, absolutely.
So that’s a really important point that our sources make, especially when they talk about the work of Noam Chomsky. So finite state machines, you know, they can capture some basic patterns that are found in language, but they really struggle with what we call long distance dependencies. Okay? And these happen when you have parts of a sentence that are grammatically linked or they’re dependent on each other, even though there might be a bunch of words in between them.
Can you give me an example of some of those dependencies that we see in language?
Of course, yeah. So think about some common structures, you know, like either or right or if then. So the fact that you have either at the beginning means that you have to have or later on right to make this sentence grammatically correct, right? We also have subject verb agreement, yes. So, for example, the dog that chased the cat Mark runs versus the dogs that chased the cat run. Yeah. So the form of the verb, you know, runs or run, right? It depends whether the subject dog or dogs is singular or plural, right? And those can be really far apart from each other. Yes, they can be in complex sentences. So
what is it about FSMS that makes it hard for them to handle these kinds of dependencies? So
it goes back to that core idea that we talked about, the fact that they are memoryless to handle those long distance dependencies, where the related parts can be, you know, really far away from each other. The machine would basically have to remember that it encountered the first part right, like, you know, either or a singular subject until it gets to the second part, like the or, or, you know, the verb in the right form, matching verb Exactly. And because FSMS have that fixed number of states, and, you know, they don’t have a way to store information about what happened a while ago. They can’t keep track of those relationships if the input gets too long or complex,
right? And our sources even mention chomsky’s argument that even if we said, okay, there’s a limit to how far apart those dependencies can be in human language, right? Right? The number of states that you would need in an FSM to accurately model that would be so huge. Be
ridiculous. It’d be totally impractical. It wouldn’t tell us anything useful, right? Would be really
complex. So the model wouldn’t really have any explanatory power. That’s, you know, a key reason why Chomsky and other linguists and cognitive scientists have said that we need more powerful models, yeah, things like context free grammars, which, you know, maybe we’ll talk about in the future, yeah, but, you know, they say we need these things to really account for how human language works exactly.
Now, moving away from language a little bit, you know, into the real world, our sources also talk about some examples where finite state machines are actually used, yeah, at least as, like a useful way of thinking about things or as a component of a bigger system. What are some of the examples they mentioned? So
we see them in everyday technology, even in like how we understand natural behavior, yeah? So a common one is the the automatic sliding door right? That’s triggered by motion, yeah? So it can be closed or open, right, and then that sensor, you know, triggers the change between those states. Yeah. We also have things like a lawn mower. A simple lawn mower might have states like off, idle and cutting right, and the user input, you know, starting the engine or engaging the blades that causes it to switch between those. Yeah, it’s interesting. The material even mentions things like a predators behavior, you know, when it’s hunting, right? It can be modeled in terms of states like searching, stocking and pouncing. Interesting and environmental cues are the things that trigger the changes there, right? And even the concept of belief states in cognitive models, oh, can be thought of in terms of FSMS.
So before we finish up this deep dive, our sources touch on a connection between finite state machines and regular expressions. Yes, you tell us a bit about that relationship and why it matters.
Absolutely, it’s a very practical and powerful link. Yeah. So it turns out that for every finite state machine that can recognize a language, there’s a regular expression that can describe the exact same language. Oh, wow, and vice versa. And regular expressions, they’re basically a way to define patterns in text. They’re very useful in computer science. You know, you use them for things like searching text, validating data and, you know, finding patterns, right? Our sources actually give a couple examples like open parentheses, AB, close parenthesis, plus sign, okay. That represents, you know, one or more repetitions of AB, right? Then we have open parenthesis, a, vertical bar, B, close parenthesis, CE, asterisk, which means either A or B, followed by CE, and then zero or more, es, okay. And the fact that FSMS and regular expressions are kind of equivalent in terms of what they can express for a certain type of language shows how important and how widely applicable this model is in computing, right? So if you can define a pattern with a regular expression, you can build an FSM that can recognize it, and if you have an FSM, you can write a regular expression for the language it accepts.
So to wrap up this deep dive, we’ve explored finite state machines, right, these computational models that have a limited number of states and transitions between them that happen based on input. Yes, we’ve looked at the key parts, like the starting state, the accepting states, those transition rules, right? We also talked about how FSMS don’t have memory, and how they can be used to define and recognize formal languages, yeah, by either accepting or rejecting different strings. We talked about how they’re not perfect for things like human language, which is really complex, right? But we also saw how they’re really important for building all kinds of technologies, and they provide a good way to understand systems that work step by step.
And for you the learner, understanding finite state machines is like, you know, having a basic tool, right? To understand computation, this idea of, you know, systems moving through different states based on specific input, yeah, it’s something you’ll probably see again and again, right? If you’re studying computer science, linguistics, or even, you know, models of how the mind works, absolutely and so this brings us to a final thought, Okay, we’ve talked about the limitations of FSMS, especially with something as complicated as human language, right? But where else you know? Could this model of transitions and limited memory be useful, right? Not just in the world, but maybe even you know how we think. Maybe you can think about everyday devices, they have different modes of operation, or just basic decision making processes, or, you know, simple biological systems that go through different phases. Okay, where else might you see these principles of the finite state machine? That’s really interesting. It’s a way of thinking to keep in mind as you continue to explore how things work. Mm, hmm.
Transcribed by https://otter.ai
Evaluation
I do feel like if this had been my experience the first time I would have understood the premise of FSMs a little more smoothly and much less convoluted than it was the first time, but it’s hard to tell when I didn’t really have visual aids. I also wish they had incorporated another main example. I feel like I would have benefitted from the variety. Like I feel like they focused so hard on one simple example with the quarter machine, but I don’t know, I’m someone who learns better from being more hands on and with examples. I found this to be a struggle the first time I learned this too. But if I had to rule, I would have to say I cannot confidently say that this could teach me better than a professor would on this, I’m more in like idk territory right now.
Another thing I notice is that they make it so obvious that this info is from a intro cogs class and that it is intended for college students, they actually plainly and obviously say so a couple of times through the podcast. I thought it was ridiculously funny.
I do think it was really interesting how real this felt. I feel like it really did feel like two people talking for the most part. My only issue was with the woman that was talking, she would randomly be saying words like “right” and “ok” and I guess that was their attempt to make it feel natural and have her acknowledging the other speaker, but it didn’t feel authentic to me. To be honest it felt like when she said that, she wasn’t even listening to the other person and was just saying that to make it seem like she was.
Concerns
When I had my experience of hearing a notebook LM for the first time in my Neuroscience and Society class, my professor did mention how often as a default it will generate two speakers - a man and a woman, and it will be the man saying the bulk of the podcast and educating the listeners, and the woman is the one that asks questions and listens. It gave off that there is a sexism concern and I was actively held this thought as I was listening to podcast to see if this still holds true. To be honest, I still think it does. I think for a lot of the podcast, especially the beginning it was mostly the man speaking in bulk, and the woman was there in the beginning being like “ok” and “right” and just listening and asking the questions. I don’t really remember the man doing the same until closer to the end really. I do think this experience though is better than than the one I had in my previous class, she talks more than I expected to be honest. But like I didn’t get the sense there was much focus on her as much as the dude. I’ve made podcasts before especially for that previous class, where there was two of us speaking, and we were still able to share the spotlight and have us both have equal parts in portraying the subject matter to our audience, so I’m kind of concerned on why Notebook LM is not completely there yet.